package 中等.前缀和与差分;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/subarray-sum-equals-k/
 */
public class 和为K的子数组_560 {

    public static void main(String[] args) {

    }

    /**
     * 以i结尾的所有子数组和为：sum[i]-sum[j-1]
     * 如果：sum[i]-sum[j-1] == k
     * <p>
     * 公式换位：sum[j-1] == sum[i]-k
     * j 的范围 [0,i] , 也就是说 sum[j] j 属于 [0,i-1]
     * 而 sum[j] 代表的是[0,j]连续数组的个数，我们可以通过迭代维护map中key为总和，
     * 出现的次数
     *
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        Map<Integer, Integer> map = new HashMap<>();
        // 当 nums[i]==k 时，sum[i]-k==0 ，即单个i索引为1个符合条件的子数组
        map.put(0, 1);
        int[] sum = new int[nums.length];
        sum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            count += map.getOrDefault(sum[i] - k, 0);
            map.put(sum[i], map.getOrDefault(sum[i], 0) + 1);
        }
        return count;
    }

    /**
     * 不需要预处理前缀和
     *
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum2(int[] nums, int k) {
        int count = 0, preSum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        // 当 nums[i]==k 时，sum[i]-k==0 ，即单个i索引为1个符合条件的子数组
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            int curSum = preSum + nums[i];
            count += map.getOrDefault(curSum - k, 0);
            map.put(curSum, map.getOrDefault(curSum, 0) + 1);
            preSum = curSum;
        }
        return count;
    }

}
